unit PtADTIntf;

interface

uses
  SysUtils;
{$WARN UNSAFE_TYPE OFF}
{$WARN UNSAFE_TYPE ON}

type
  TADTElemData  = TObject;

  //  Element types

  //  Used for ADTs that do NOT require keys
  IADTElement = interface
  ['{78EF58B6-6DB7-4BE0-9843-6F14B5FF35D7}']
    function  Data: TADTElemData;
  end;

  //  Used for ADTs that DO require keys
  IADTKey = interface(IADTElement)
  ['{97C6E3FA-C149-4864-9C52-09EDEC63920E}']
    function  ComparedTo(const Key: IADTKey): integer;
  end;

  //  Container types

  //  Used for ADTs that do NOT require keys
  ISimpleContainer = interface
  ['{5AF0045F-7018-42A6-A046-481DDBF8FF39}']
    procedure Push(const Data: IInterface);
    function  Pop: IInterface;
    function  IsEmpty : Boolean;
  end;

  //  Used for ADTs that DO require keys
  IContainer = interface
    procedure Add(const Key: IADTKey);
    function  Remove(const Key: IADTKey): IADTKey;
    function  Find(const Key: IADTKey): IADTKey;
  end;

  //  Implementation of stack and queue

  PElement = ^TElement;
  TElement = record
    Next  : PElement;
    Data  : IInterface;
  end;

  TSimpleContainer = class(TInterfacedObject)
  protected
    procedure DisposeAll(const Elem: PElement);
  public
    destructor  Destroy; override;
    procedure Clear; virtual; abstract;
  end;

  TStack = class(TSimpleContainer, ISimpleContainer)
  private
    fLast   : PElement;
  public
    procedure Push(const Data: IInterface);
    function  Pop: IInterface;
    function  IsEmpty: Boolean;
    procedure Clear; override;
  end;

  TQueue = class(TSimpleContainer, ISimpleContainer)
  private
    fFirst  : PElement;
    fLast   : PElement;
  public
    procedure Push(const Data: IInterface);
    function  Pop: IInterface;
    function  IsEmpty: Boolean;
    procedure Clear; override;
  end;

  //  Implementation of linked list

  PListNode = ^TListNode;
  TListNode = record
    Next  : PListNode;
    Data  : IADTKey;
  end;

  EADTIntf = class(Exception)
  end;

implementation

const
  SCannotPopEmpty = 'Cannot pop from an empty ';

{ TSimpleContainer }

destructor TSimpleContainer.Destroy;
begin
  Clear;
  inherited;
end;

procedure TSimpleContainer.DisposeAll(const Elem: PElement);
begin
  if  Elem <> nil then
    begin
      DisposeAll( Elem.Next );
      Dispose( Elem );
    end;
end;

{ TStack }

procedure TStack.Clear;
begin
  DisposeAll( fLast );
end;

function TStack.IsEmpty: Boolean;
begin
  Result  := fLast = nil
end;

function TStack.Pop: IInterface;
var
  Elem  : PElement;
begin
  if  IsEmpty then
    raise EADTIntf.Create( SCannotPopEmpty+ClassName );
  Elem    := fLast;
  Result  := Elem.Data;
  fLast   := Elem.Next;
  Dispose( Elem );
end;

procedure TStack.Push(const Data: IInterface);
var
  Elem  : PElement;
begin
  New( Elem );
  Elem.Data := Data;
  Elem.Next := fLast;
  fLast     := Elem;
end;

{ TQueue }

procedure TQueue.Clear;
begin
  DisposeAll( fFirst );
end;

function TQueue.IsEmpty: Boolean;
begin
  Result  := fFirst = nil
end;

function TQueue.Pop: IInterface;
var
  Elem  : PElement;
begin
  if  IsEmpty then
    raise EADTIntf.Create( SCannotPopEmpty+ClassName );
  Elem    := fFirst;
  Result  := fFirst.Data;
  fFirst  := fFirst.Next;
  Dispose( Elem );
end;

procedure TQueue.Push(const Data: IInterface);
var
  Elem  : PElement;
begin
  New( Elem );
  Elem.Data   := Data;
  Elem.Next   := nil;
  if  fFirst = nil  then
    fFirst      := Elem
  else
    fLast.Next  := Elem;
  fLast       := Elem;
end;

end.
